class Solution
{
    int ret = 0, refer = 0;
    int n = 0, m = 0;
    bool check[21][21];
public:
    int uniquePathsIII(vector<vector<int>>& grid)
    {
        n = grid.size();
        m = grid[0].size();

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == 0)
                    ++refer;
                if (grid[i][j] == -1)
                    check[i][j] = true;
            }
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == 1)
                {
                    check[i][j] = true;
                    dfs(grid, i, j, 0);
                    check[i][j] = false;
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int row, int col, int count)
    {
        if (grid[row][col] == 2)
        {
            if (count == refer)
                ++ret;
            return;
        }
        if (row - 1 >= 0 && !check[row - 1][col])
        {
            check[row - 1][col] = true;
            dfs(grid, row - 1, col, grid[row][col] == 0 ? count + 1 : count);
            check[row - 1][col] = false;
        }
        if (row + 1 < n && !check[row + 1][col])
        {
            check[row + 1][col] = true;
            dfs(grid, row + 1, col, grid[row][col] == 0 ? count + 1 : count);
            check[row + 1][col] = false;
        }
        if (col - 1 >= 0 && !check[row][col - 1])
        {
            check[row][col - 1] = true;
            dfs(grid, row, col - 1, grid[row][col] == 0 ? count + 1 : count);
            check[row][col - 1] = false;
        }
        if (col + 1 < m && !check[row][col + 1])
        {
            check[row][col + 1] = true;
            dfs(grid, row, col + 1, grid[row][col] == 0 ? count + 1 : count);
            check[row][col + 1] = false;
        }
    }
};